// hi_dw.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "myHead.h"//

#include <iostream>
using namespace std;
#include <stack>


int * q_sort_1(int *arr,int l ,int r){

	//assert arr
	if(l>=r)
		return arr;

	int i,index;
	
	//j
	index=l;
	int vaule_index=arr[index];  //!! 还少了这个

	for(i=    index+1; i<=r; i++){
		//if( arr[   index]  <   arr[i])						//!!不要加=
		if(  arr[i] < vaule_index)							//!!不要加=
			mySwap(&arr[     ++ index] , & arr[i]);//++index 就是这样
	}

			mySwap(&arr[      index] , & arr[l]); // ！！再一次出错！ left ,not i

//划分出Index,not i

	//recursive

			q_sort_1(arr,0,   index-1);
			q_sort_1(arr,index+1,r);

	return NULL;//tmp 

	//高频出错点 swap() 比较，
}


void q_sort_2_珠玑_2(int a[], int l, int u)
{
	if(l >= u)
		return;
	int m = l;
	int i = l+1;
	int j = u;
	while(i<=j)
	{
		while(a[i]<a[m])
			i++;
		while(a[j]>=a[m]&&j>m)
			j--;
		if(i<j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	int temp = a[m];
	a[m] = a[j];
	a[j] = temp;
	q_sort_2_珠玑_2(a, l, j-1);
	q_sort_2_珠玑_2(a, j+1, u);
}

int *q_sort_2_珠玑(int *arr,int l, int r)//后面来个随机数
{
	if(l>=r)
		return arr;
	//
	int i_l=l ;	//+1;
	int i_r=r+1;  //对称的，如果都， i_1=i+1,i_r=r 下面都用while ,not do while
	int index=l;//轴
	while(1){
		do{i_l++; }												//do while
		while(  i_l <=r  && arr[i_l]<arr[index]  ) ; //！！ 不要取等,上限

		do{ i_r--;	}
		while(i_r>=l && arr[i_r] >arr[index]  )		;			//减法
 
		if(i_l>i_r)//          取等吗？ 淘宝上没有取等
			break;
		Swap_3(arr,i_l,i_r);
	}
		Swap_3(arr,i_l,index);//轴恢复

	//start recresive
	
//q_sort_2_珠玑(arr,0,i_l -1);
//q_sort_2_珠玑(arr,i_l +1 ,r);

q_sort_2_珠玑(arr,0,i_r -1); //i_j偏小
q_sort_2_珠玑(arr,i_r +1 ,r);
	
}



void  *q_sort_2_教材(int *arr,int l,int r){
//assert arr, l==r
	if(l>=r )return NULL;

	int i_left=l+1,i_right=r;  //这样换就是除开l,剩余区间，并且
	int index=l;
	int value=arr[index];

	while(   i_left<i_right  ){//!! 不能加=====

		while(i_left<i_right &&    arr[i_right]>=value )  i_right--;  //!!
		//Swap_3(arr,i_right,index);
		
		if(i_left<i_right ){
		arr[index] = arr[i_right]; index = i_right;
		}

		while(i_left<i_right &&    arr[i_left] < value) i_left++;
		//Swap_3(arr,i_left,index);

		if(i_left<i_right )//太强了。。
		{
			arr[index] = arr[i_left]; index = i_left;
		}

	}

	arr[index] = value;

	//左边i_left 作为轴，一般情况 =i_right

q_sort_2_教材(arr,0,index-1);		//这里选用左 还是 右啦？
q_sort_2_教材(arr,   index+1,r);



//特别注意：只有一个地方使用 arr[index],比较的时候不用。。 还有这里的条件是不是太强了
//调试的时候注意恢复现场。几个改变指针的程序 同时运行，当然bug..
//还有一点，，书本上的，就没有使用 swap...!! //李朋说的 填坑。。！！
}




void test_Qsort(){
const int index=2;
	int arr[2][5]={{1,2,3,4,5},{5,4,3,2,1}}; //第一个可以不定
	int tmp[]={9,8,7,6,5};

	int *arr_res;
	
			//arr_res=q_sort_1 (tmp,0,4);	//问题是区间没有减少， 至少 在单向遍历时3个错误。fail 
		//q_sort_2_珠玑_2(tmp,0,4);
	
		q_sort_2_教材 (tmp,0,4);			//第一个通过，输出结果。但是结果不对，估计是 里面的while问题。
		//print_Arr(tmp,4);			 //直接看debug时返回的 一维数组。

			//arr_res=q_sort_2_珠玑 (tmp,0,4);  //同样区间灭有 减少！  //修正了 递归的边界为 右边的游标 i_right
//---------------------
	//arr_res=q_sort_1 (arr[0],0,4);
	//print_Arr(arr_res,4);
	//arr_res=q_sort_1 (arr[1],0,4);
	//print_Arr(arr_res,4);

		//收获：堆栈程序 堆栈溢出
	//3个版本第一轮 not pass
}

//func:
//return:
//@param:

int computeUnit(char oprand,int l,int r)
{
	int rel;
	if ( oprand=='+')
	{rel=l+r;
	} 
	else if(oprand=='-')
	{rel=l-r;
	}
	else if(oprand=='*')
	{rel=l*r;
	}
return rel;
}

int ReversePoland(char *input){

	//assert

	//2...
	int rel=0;
	 
	stack<char > mystack_oprand;
	//stack<char> mystack_Poland;//混合
	char *str_Poland=new char(21);
	stack< int>     mystack_num;
	static int  index=0,mutli_index=0;

	int left_num=0,right_num=0;
	char myoprand=NULL,char_tmp=NULL;


	char *index_Poland=str_Poland;

	while(*input !=NULL){

/************************************************************************/
/*                                                                      */
/************************************************************************/		
		//switch()
//判断字符

		//if ('0'<=*input 
		//	&&*input<='9'
		//	&& *input=='('
		//	&& *input==')'
		//	&& *input=='+'
		//	&& *input=='-'
		//	)//暂时支持,no 除法
		//{//ok
		//}
		//else
		//{
		//return -1;//负数
		//}

/************************************************************************/
/* 2                                                                     */
/************************************************************************/
		index++;//方便 辨认多位符号。
		int mynum=0,num_tmp;
		if ('0'<=*input 
			&& *input<='9'){				 //lp help me !! bug 
				mynum=*input -'0' ;  //lp help me !!
			*index_Poland=*input;
				index_Poland++;
		}//处理数字

/************************************************************************/
/* 运算符                                                                     */
/************************************************************************/
		
 		if ('(' == *input)
		{mystack_oprand.push('(');
		} 
		else if(')' == *input)
		{
			//出战到(
			while (mystack_oprand.top()!='(')
			{
	/*			right_num=mystack_num.top();
				mystack_num.pop();
				left_num  =mystack_num.top();
				mystack_num.pop();*/
				
				myoprand=mystack_oprand.top();
				mystack_oprand.pop();

				*index_Poland=myoprand;
				index_Poland++;//

			}
			//add
			//clear '('
			mystack_oprand.pop();
		}//else if(')' == *input) 
		else if('+' == *input ||
				'-' == *input ||
				'*' == *input 
			) {
				//三种判断

				if ( mystack_oprand.empty()==true 
					||
						('*'!= mystack_oprand.top()&&
						 '*'==*input  //1+2*3 ,when *push in
						)
					|| '('== mystack_oprand.top()
					)
				{
				 	mystack_oprand.push(*input);

		

				}
				else{//输出到串
					char_tmp=mystack_oprand.top();
					mystack_oprand.pop();
					
					mystack_oprand.push(*input);//	//遗漏！！ 

					*index_Poland=char_tmp;
					index_Poland++;		//


				}//else

		}//
		
	
		input++;
	}//while(*input !=NULL){ 


/************************************************************************/
/*          计算模块，要么push,要么计算                                                            */
/************************************************************************/
	while(mystack_oprand.empty() !=true){
		*index_Poland++ = mystack_oprand.top();
		mystack_oprand.pop();
	
	}//李朋辅助 ！！

	*index_Poland=NULL;//end

	index_Poland=str_Poland;
	int mynum;
	rel=0;
while(*index_Poland!=NULL)
{
	mynum=0;
	if ( '0'<=*index_Poland &&
		*index_Poland<='9'
		)
	{
		mynum=*index_Poland-'0';
		mystack_num.push(mynum);
	}
	else
	{

		right_num=mystack_num.top();
		mystack_num.pop();
		left_num  =mystack_num.top();
				/************************************************************************/
				/* 关于多个数字，小数点再次处理                                                                     */
				/************************************************************************/
		mystack_num.pop();
		rel=computeUnit(*index_Poland,left_num,right_num);//考虑 有空的情形吗？
		mystack_num.push(rel);
	}

	index_Poland++;


}

	// delete str_Poland;// 有报错，内存！！暂时注释。。
	return rel;


	//1+2+3;

	//mystack_num.push()//atoi(const_cast<char >(*input)) );


/************************************************************************/
/* 处理多个输入的方案                   10+2                                                   */
/************************************************************************/
//mystack_Poland.push(mystack_num);//！！发现问题就是 在波兰表达式中不能这么处理的，只能单个字符
}
	//竟然被大富豪 能难住了
void test_RPoland(){
	char tmp[][20]={
			"1+2+3",
		"1+2*3",
		"(1+2)*3",
		"5+2-1*2+5",//bug
		"5+2-10*2+5" //bug
	};
	//安排，暂时不安排 两位的，不含除法，
	int rel;

	rel=ReversePoland(tmp[3]);
	printf("%s =%d\n",tmp[3],rel);//bug

	rel=ReversePoland(tmp[2]);
	printf("%s =%d\n",tmp[2],rel);


	 rel=ReversePoland(tmp[0]);
		printf("%s =%d\n",tmp[0],rel);

		 rel=ReversePoland(tmp[1]);
		printf("%s =%d\n",tmp[1],rel);

	
/************************************************************************/
/* 负数，小数，大数以后考虑。除法                                                                     */
/************************************************************************/

//转换前的栈 ，转换后的栈，还有中间输出的，all 一起了。
}


int _tmain(int argc, _TCHAR* argv[]) //不用递归的树！！ 我的老电脑中烤出啦
{
	//test_Qsort();
		test_RPoland();

getchar();
return 0;
}



